package LeetCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

//
// Created by ✎﹏ℳ๓独赏☆独醉 on 2024/5/16.
//
//https://leetcode.cn/problems/combination-sum-ii/description/
public class 组合总和II {
    public static void main(String[] args) {
        int[] nums = {10,1,2,7,6,1,5};
//        System.out.println(nums.length);
        int target = 8;
        List<List<Integer>> res = combinationSum2(nums,target);
        System.out.println(res);
    }
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if(candidates.length == 0)return res;
        List<Integer> temp = new ArrayList<Integer>();
        Arrays.sort(candidates);
        dfs(res,temp,candidates,target,0,0);
        return res;
    }
    private static void dfs(List<List<Integer>> res, List<Integer> temp,int[] candidates, int target, int tempIndex, int step) {
        // TODO Auto-generated method stub
        for (int i = tempIndex; i < candidates.length; i++) {
            if(target - candidates[i] < 0)return;
            if(i > tempIndex && candidates[i] == candidates[i - 1])continue;
            if(target - candidates[i] == 0){
                temp.add(candidates[i]);
                if(!res.contains(temp)){
                    List<Integer> t = new ArrayList<Integer>(temp);
                    res.add(t);
                }
                temp.remove(step);
                return;
            }
            if(target - candidates[i] > 0){
                temp.add(candidates[i]);
                dfs(res, temp, candidates, target - candidates[i], i + 1, step + 1);
                temp.remove(step);
            }
        }
    }


}

//    private static void dfs(int[] candidates,List<Integer> temp, int target,int ti, int step) {
//        for (int i = ti; i < candidates.length; i++) {
//            if(target - candidates[i] > 0){
//                temp.add(candidates[i]);
//                dfs(candidates,temp,target-candidates[i],i + 1,step + 1);
//                temp.remove(step);
//                continue;
//            }
//            if(target - candidates[i] == 0){
//                temp.add(candidates[i]);
//                return;
//            }
//            if(target - candidates[i] < 0){
//                break;
//            }
//        }
//    }